package algorithm.slidingWindow;

import java.util.HashMap;
import java.util.Map;

// 水果成篮
public class LC904 {
    // 优化的版本 -> 用技术数组代替容器
    public int totalFruit(int[] fruits) {
        int l = 0, r = 0, n = fruits.length, ans = 0, kinds = 0;
        int[] hash = new int[n+1];

        while (r < n) {
            int in = fruits[r];
            if (hash[in] == 0) kinds++;
            hash[in]++;
            while (kinds > 2) {
                int out = fruits[l];
                hash[out]--;
                if (hash[out] == 0) kinds--;
                l++;
            }
            ans = Math.max(ans, r - l + 1);
            r++;
        }
        return ans;
    }

    // 使用容器的版本
    public int totalFruit1(int[] fruits) {
        int l = 0, r = 0, n = fruits.length, ans = 0;
        Map<Integer, Integer> map = new HashMap<>();

        while (r < n) {
            map.put(fruits[r], map.getOrDefault(fruits[r], 0)+1);
            while (map.size() > 2) {
                int lVal = map.get(fruits[l]);
                map.put(fruits[l], --lVal);
                if (lVal == 0) map.remove(fruits[l]);
                l++;
            }
            ans = Math.max(ans, r - l + 1);
            r++;
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] arr = {3,3,3,1,2,1,1,2,3,3,4};
        LC904 lc904 = new LC904();
        System.out.println(lc904.totalFruit(arr));
    }
}
